//给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。 
//
// 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列
//，而 "AEC" 不是） 
//
// 题目数据保证答案符合 32 位带符号整数范围。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "rabbbit", t = "rabbit"
//输出：3
//解释：
//如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
//rabbbit
//rabbbit
//rabbbit 
//
// 示例 2： 
//
// 
//输入：s = "babgbag", t = "bag"
//输出：5
//解释：
//如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
//babgbag
//babgbag
//babgbag
//babgbag
//babgbag
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length, t.length <= 1000 
// s 和 t 由英文字母组成 
// 
// Related Topics 字符串 动态规划 👍 751 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

class DistinctSubsequences {
    public static void main(String[] args) {
        Solution solution = new DistinctSubsequences().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int numDistinct(String s, String t) {
            // dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
            int[][] dp = new int[s.length() + 1][t.length() + 1];
            // 初始化左上两边
            dp[0][0] = 1;   // s为0，t为0，那么空字符串s删除元素之后编程空字符串t（特殊情况）
            for (int i = 1; i < s.length() + 1; i++) {
                dp[i][0] = 1;   // s中删除元素，删除到空字符时和空字符t匹配，所以有一种
            }

            for (int i = 1; i < t.length(); i++) {
                dp[0][i] = 0;   // s为空，那么怎么删除都不可能会和t项匹配
            }

//            这一类问题，基本是要分析两种情况
//            s[i - 1] 与 t[j - 1]相等
//            s[i - 1] 与 t[j - 1] 不相等
//            当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。
//            一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。
//            一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 1; j <= t.length(); j++) {
                    if (s.charAt(i - 1) == t.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; // 注意时s中包含t，所以是 i - 1 而不是 j - 1
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }

            return dp[s.length()][t.length()];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
